1. Field of the Invention
The present invention relates to an associative memory having a plurality of word memories each for storing storage data in units of words, in which a retrieval of the word memories storing predetermined storage data is performed using applied reference data.
2. Description of the Related Art
Hitherto, there has been proposed an associative memory or a content addressable memory provided with the retrieval function as mentioned above.
FIG. 14 is a circuit block diagram of the conventional associative memory by way of example.
Referring to FIG. 14, an associative memory 10 is provided with a number of word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n each consisting of a m-bit of memory cell, arranged in a transverse direction of the figure, a word being expressed with "m" bits. Further, the associative memory 10 comprises a reference data register 12 which is adapted to latch a word of reference data when it is applied thereto, and a mask data register 13 arranged to store mask data to mask the reference data for each bit. A bit pattern of the non-masked data, which is the whole excepting one masked on the basis of the mask data stored in the mask data register 13 or a specified part, among the reference data latched in the reference data register 12 is compared with a bit pattern of the portion corresponding to the bit pattern of the latched reference data with respect to data stored in each of the word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n. As a result of the comparison, if there are found any of the word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n of which the bit pattern is coincident with that of the reference data, a match signal expressed as a logic "1" will appear on the associated ones of match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n which are provided in conjunction with the word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n, respectively. On the other hand, a mismatch signal expressed as a logic "0" will appear on the remaining ones of the match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n.
The signals supplied to the match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n are stored in match flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n, respectively. Now, assuming that the signals "0", "1", "1", "0", . . . , "0", "0" appear on the match flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n, respectively, these signals are applied to an address encoder 16. The address encoder 16 is so arranged to output an address signal corresponding to the highest priority match flag register given with a highest priority among the match flag registers (here, only two match flag registers 15.sub.-- 2 and 15.sub.-- 3) which store the signals given by a logic "1". Supposing that the priority is higher as number of a suffix of the reference numeral becomes younger, in this case, the memory address associated with the match flag register 15.sub.-- 2 is outputted. Thus, an address encoder 16 outputs an address signal AD corresponding to the highest priority match flag registers 15.sub.-- 2, which address signal AD may be passed to an decoder 17, if necessary. The decoder 17 decodes the received address signal AD and outputs an access signal to the associated one (here a word line 18.sub.-- 2) of word lines 18.sub.-- 1, 18.sub.-- 2, . . . , 18.sub.-- n which are provided in conjunction with the word memories ]11, 11.sub.-- 2, . . . , 11.sub.-- n, respectively. Thus, data stored in the word memory 11.sub. -- 2 associated with the word line 18.sub.-- 2 on which the access signal appears is read out to an output register 19.
Next, change of the signal "1" stored in the match flag register 15.sub.-- 2 to "0" makes it possible now to derive an address of the word memory 11.sub.-- 3 associated with the match flag register 15.sub.-- 3.
FIG. 15 is a functional block diagram of the conventional associative memory.
Applied to the associative memory are function data FUN.sub.-- DATA and reference data REF.sub.-- DATA. The function data FUN.sub.-- DATA serves to define the function of the associative memory. For example, when the function data FUN.sub.-- DATA takes binary number "01", it implies that the reference data REF.sub.-- DATA, which is simultaneously applied, is a mask data, and thus such data is stored in a mask data register. On the other hand, when the function data FUN.sub.-- DATA takes binary number "10", a retrieval is performed using the simultaneously applied reference data REF.sub.-- DATA. The entered reference data REF.sub.-- DATA is masked on the basis of mask data stored in the mask data register, and then supplied via a data line drive circuit to the respective word memories. When data stored in any of the word memories is coincident with the entered data, a match signal expressed by a logic "1" is stored in the associated match flag register.
As described above, according to the associative memory 10, the contents or data stored in a number of word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n are retrieved using the reference data in its entirety or a part specified, so that an address of the word memory involved in the matched data is generated, and in accordance with the necessity the whole data stored in the word memory can be read out.
In the retrieval of data using the associative memory as mentioned above, in a case where data to be retrieved is formed in a group structure, specifically, in a case where a plurality of data constituting a group are each provided with the associated attribute, the associative memory as mentioned above encounters several problems to be solved.
The first one of those problems is involved in the point as to how to retrieve a desired data from among a number of data formed in a group structure. The first problem will be explained referring to the drawings hereinafter.
FIG. 16 is an illustration showing arrays of data each being provided with an attribute, which are stored in the associative memory.
It is assumed that a number of word memories, which constitute the associative memory, are segmented into groups each consisting of four pieces of word memory as a set. The first word memory of each set stores data to which "attribute 0" such as, for example, "name", is appended, the second word memory of each set stores stores data to which "attribute 1" such as, for example, "the day of one's birth", is appended, and hereafter similarly, the third word memory and the fourth word memory store data to which "attribute 2" and "attribute 3" are appended, respectively. Here, the data stored in the word memories are denoted by the letters of the English alphabet, such as A, B, . . . . Incidentally, a set of data group, to each data of which the associated attribute is appended as mentioned above, is referred to as a "data set", hereinafter.
It happens, as shown in FIG. 16, that there are stored data involved in the same bit pattern, but different in the attribute, as being provided in such a way that data related to the attribute 0 depicted at the highest stage of FIG. 16 is of "A", and data related to the attribute 1 depicted at the subsequent stage is also of "A".
In this situation, when it is desired to retrieve only data "A" (for example, name "A") belonging to the attribute 0, if data "A" is inputted in the form of reference data, the retrieval is made for not only data "A" belonging to the attribute 0 but also data "A" belonging to other attributes 1, 2 and 3. This needs such an additional retrieval operation that after the preceding retrieval operation the data belonging to the attribute 0 is again discriminated from among the data retrieved in the preceding retrieval operation. This operation is extremely troublesome, and it takes a lot of time for the discrimination.
The second problem, which will arise when data formed in a group structure or data set is retrieved, is involved in the point as to how to enhance a flexibility of the retrieval.
While the retrieval of individual data, for example, data "A" to which the `attribute 0` is appended, data "B" to which the `attribute 2` is appended, etc., can be implemented in some way, it becomes a problem how to retrieve the data set including, for example, both the data "A" to which the `attribute 0` is appended and the data "B" to which the `attribute 2` is appended.
In this case, as stated above, it is assumed that the retrieval of individual data, such as data "A" to which the `attribute 0` is appended, data "B" to which the `attribute 2` is appended, etc., can be implemented. Consequently, the retrieval is carried out, usually, in such a manner that a number of data sets, each including data "A" to which the `attribute 0` is appended, are retrieved, and in addition a number of data sets, each including data "B" to which the `attribute 2` is appended, are retrieved. According to such a scheme, there is need to discriminate again the data sets which satisfy both the data "A" to which the `attribute 0` is appended and the data "B" to which the `attribute 2` is appended. Hence, similar to the first problem as mentioned above, this operation is extremely troublesome, and it takes a lot of time for the discrimination.
Further, in the prior arts concerning the associative memory, there is known a technology as to expansion of the data width as an object of a match retrieval into two or more words, in a case where usual data are treated, but not in a case where data formed in a group structure are treated. Such a technology will be explained hereinafter.
FIG. 17 is a block diagram of an associative memory, by way of example, provided with a data expansion function. In FIG. 17, the same parts are denoted by the same reference numbers as those of FIG. 14, and the redundant description will be omitted.
Match lines 14.sub.-- 1, 14.sub.-- 2, . . . , which are extended from the word memories 11.sub.-- 1, 11.sub.-- 2, . . . , respectively, are connected to ones of two input terminals of AND gates 20.sub.-- 1, 20.sub.-- 2, . . . , respectively. Connected to the other ones of the two input terminals of the AND gates 20.sub.-- 2, 20.sub.-- 3, . . . are output terminals of OR gates 21.sub.-- 2, 21.sub.-- 3, . . . , respectively. Ones of two input terminals of the OR gates 21.sub.-- 2, 21.sub.-- 3, . . . are connected to a first time retrieval control line 22. An OR gate associated with the AND gates 20.sub.-- 1 is omitted. The other input terminal of the AND gates 20.sub.-- 1 is directly connected to the first time retrieval control line 22.
Output terminals of the AND gates 20.sub.-- 1, 20.sub.-- 2, . . . are connected to data input terminals of first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . , respectively. Output terminals of the first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . are connected to input terminals of second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . , respectively. Output terminals of the second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . are connected to the priority encoder 16 shown in FIG. 14 (omitted in FIG. 17), respectively, and in addition to the other ones of the input terminals of the OR gates 21.sub.-- 2, 21.sub.-- 3, . . . , respectively.
Pairs of first and second flag registers 23.sub.-- 1, 24.sub.-- 1; 23.sub.-- 2, 24.sub.-- 2; . . . correspond to the flag registers 15.sub.-- 1; 15.sub.-- 2, . . . shown in FIG. 14, respectively.
Applied to both the first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . and the second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . are a match result latch signal S1 which appears on a match result latch control line 25, so that input data entered from the respective data input terminals are latched. In the first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . , there are latched the input data involved in the time point of a rise-up edge a of the match result latch signal S1. On the other hand, in the second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . , there are latched the input data involved in the time point of a trailing edge b of the match result latch signal S1.
In the associative memory arranged as mentioned above, a match retrieval is performed in accordance with a manner as described below. It is now assumed, as shown in FIG. 17, that the word memories 11.sub.-- 1, 11.sub.-- 2, 11.sub.-- 3, 11.sub.-- 4, 11.sub.-- 5, 11.sub.-- 6, . . . , store retrieval data A, B, C, D, E, F, . . . respectively.
To retrieve solely individual retrieval data, a first time retrieval timing signal $2 is supplied to the first time retrieval control line 22, when the retrieval is performed through inputting the reference data REF-DATA. Assuming that data "B" is inputted as the reference data REF-DATA, a logic "1" of match signal appears on the match line 14.sub.-- 2 associated with the word memory 11.sub.-- 2 in which data "B" has been stored, and is supplied to the AND gate 20-2. Simultaneously, the first time retrieval timing signal S2 is supplied via the first time retrieval control line 22 through the OR gate 21.sub.-- 2 to the AND gate 20.sub.-- 2. As a result, the AND gate 20.sub.-- 2 produces a logic "1" of signal. On the other hand, since logic "0" of signals appear on the other match lines 14.sub.-- 1, 14.sub.-- 3, 14.sub.-- 4, . . . , respectively, the associated AND gates 20-1, 20.sub.-- 3, 20.sub.-- 4, . . . produce logic "0" of signals, respectively.
The logic "1" of signal outputted from the AND gate 20.sub.-- 2 is latched by the first flag register 23.sub.-- 2 in timing of the rise-up edge a of the match result latch signal S1 appearing on the match result latch control line 25, and then latched by the second flag register 24.sub.-- 2 in timing of the subsequent trailing edge b of the match result latch signal S1.
On the other hand, logic "0" of signals are latched by the other first flag registers 23.sub.-- 1, 23.sub.-- 3, 23.sub.-- 4, . . . in the same timing as the logic "1" of signal is latched by the first flag register 23.sub.-- 2, and logic "0" of signals are latched by the other second flag registers 24.sub.-- 1, 24.sub.-- 3, 24.sub.-- 4, . . . in the same timing as the logic "1" of signal is latched by the second flag register 24.sub.-- 2.
In this manner, signals expressed by logic "0", "1", "0", . . . , which are latched by the second flag registers 24.sub.-- 1, 24.sub.-- 2, 24.sub.-- 3, . . . , respectively, are supplied to the priority encoder 16 as shown in FIG. 14 to generate an address signal AD of the word memory 11.sub.-- 2.
Next, there will be explained such a case where a retrieval involved in expansion of the data width is performed. Here, a case where two-word data consisting of data "B" and data "C" is retrieved, by way of example, will be explained.
In the same manner as the above-mentioned case, first, a retrieval of the data "B" is performed. As a result, signals expressed by logic "1" are latched by the first flag register 23.sub.-- 2 and the second flag register 24.sub.-- 2, respectively, which are associated with the word memory 11.sub.-- 2. Next, the data "C" is inputted as the reference data REF-DATA for retrieval. At that time, the time retrieval timing signal S2 is not supplied to the first time retrieval control line 22, and the first time retrieval control line 22 is kept logic "0". Performing the retrieval through inputting the data "C" as the reference data REF-DATA will induce match signals expressed by logic "1" on the match lines 14.sub.-- 3 and 14.sub.-- 5 which are associated with the word memories 11.sub.-- 3 and 11.sub.-- 5, respectively. Since the logic "1" of signal latched by the second flag register 24.sub.-- 2 has been supplied to the OR gate 21.sub.-- 3, the match signal appearing on the match line 14.sub.-- 3 is passed via the AND gate 20.sub.-- 3 to the first and second flag registers 23.sub.-- 3 and 24.sub.-- 3, so that a signal expressed by logic "1" representative of a match is latched by the first and second flag registers 23.sub.-- 3 and 24.sub.-- 3. On the other hand, since the logic "0" of signal latched by the second flag register 24.sub.-- 4 has been supplied to the OR gate 21.sub.-- 5, the match signal appearing on the match line 14.sub.-- 5 is inhibited by the AND gate 20.sub.-- 5, so that a signal expressed by logic "0" representative of a mismatch is latched by the first and second flag registers 23.sub.-- 5 and 24.sub.-- 5. In this manner, there is carried out a match retrieval for two-word data consisting of a pair of data "B" and data "C". Likewise, a match retrieval for three-word data or more word data may be implemented.
While the associative memory shown in FIG. 17 is provided with a data width expansion function, it is necessary for data to be expanded to two-word, three-word and so on to be stored in mutually adjacent word memories in a predetermined order, and thus it is impossible to perform a match retrieval in combination of plural data, in a case where they are stored in the reversed order, for example, in sequence of data "C" and data "B", or in a case where they are stored in mutually distant word memories. That is, the above-mentioned data width expansion function is unsuitable for retrieval of data formed in a group structure.
Further, in case of retrieval using an associative memory, hitherto, there is a case in which an object of retrieval is attained through performing a successive plural number of times of retrieval, for example, such a case that independently of data of a group structure being treated, an associative memory (e.g. FIG. 17) into which a data width expansion function is incorporated is used to implement retrieval using the data width expansion function. Likewise, also in a case where data of the group structure is treated as an object of retrieval, there may be a case in which an object of retrieval is attained through performing a successive plural number of times of retrieval, for example, as mentioned above, such a case that a match as to a plurality of data within a single data set is retrieved. In this case, there encounters a problem, as the third problem, how the associative memory is constituted to effectively implement a successive plural number of times of retrieval for data of a group structure having more complicated data structure. Specifically, there is not at all known a technology concerning a structure of an associative memory capable of retrieving at high speed and flexibly group structure of data which needs random and plural retrievals, and utilization of associative memories as well.